/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
    let nums2Stack = [],
        nums2NextGreater = new Array(nums2.length).fill(-1),
        nums1NextGreater = new Array(nums1.length).fill(-1);

    for (let i = 0; i < nums2.length; i++) {
        // 即将入栈的元素大于栈顶元素
        while (nums2Stack.length > 0 && nums2[i] > nums2[nums2Stack[nums2Stack.length - 1]]) {
            let topIndex = nums2Stack.pop()
            nums2NextGreater[topIndex] = nums2[i]
        }

        // 即将入栈的元素小于或等于栈顶元素
        nums2Stack.push(i)
    }

    for (let i = 0; i < nums1.length; i++) {
        nums1NextGreater[i] = nums2NextGreater[nums2.indexOf(nums1[i])]
    }

    return nums1NextGreater
};



/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
    let nums2Stack = [],
        nums2NextGreaterMap = new Map(),    // 用map代替数组，查找速度更快，虽然leetcode上提交时并没有更快
        nums1NextGreater = new Array(nums1.length).fill(-1);

    for (let i = 0; i < nums2.length; i++) {
        while (nums2Stack.length > 0 && nums2[i] > nums2[nums2Stack[nums2Stack.length - 1]]) {
            let topIndex = nums2Stack.pop()
            nums2NextGreaterMap.set(nums2[topIndex], nums2[i])
        }

        nums2Stack.push(i)
    }

    for (let i = 0; i < nums1.length; i++) {
        nums1NextGreater[i] = nums2NextGreaterMap.get(nums1[i]) || -1
    }

    return nums1NextGreater
};